package 剑指offer;

public class p26树的子结构 {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //主函数：A树的子结构 是否有 和 B树相同，因此是 或 的关系
        if (A==null || B==null) {
            return false;
        }

        return isSub(A,B) || isSubStructure(A.left,B) ||isSubStructure(A.right,B);
    }

    private boolean isSub(TreeNode a, TreeNode b) {
        //isSub函数：当前a树 和 目标b树 是否相同，需要根节点、左子树、右子树都相等，因此是 且 的关系
        if (b==null) {
            return true;
        }

        //b不为空，但 a为空，或者两个节点的值不同
        if (a==null || a.val!=b.val) {
            return false;
        }
        return isSub(a.left,b.left) && isSub(a.right,b.right);
    }
}
